package algorithm;

public class MergeSort {

    public static void mergeSort(){
        int[] arr={2,12,5,4,8,7,9,8,10};
        process(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void process(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        int M=L+((R-L)>>1);
        process(arr,L,M);
        process(arr,M+1,R);
        merge(arr,L,M,R);
    }

    public static void mergeSort2(int[] arr){
        if(arr==null){
            return;
        }
        int mergeSize=1;
        int L=0;
        int R;
        int M;
        while(mergeSize<arr.length){
            L=0;
            while (L<arr.length-1){
                M=L+mergeSize-1;
                if(M>=arr.length-1)
                    break;
                if(M+mergeSize>arr.length-1){
                    merge(arr,L,M,arr.length-1);
                    break;
                }
                R=M+mergeSize;
                merge(arr,L,M,R);
                L=R+1;
            }

            if(mergeSize>=(arr.length>>1)+1)
                break;
            mergeSize*=2;
        }
    }

    public static void merge(int[] arr, int L, int M, int R){

        int i=0;
        int[] help=new int[R-L+1];
        int p1=L;
        int p2=M+1;
        while (p1<=M&&p2<=R){
            help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        if (p1>M){
            while(i<help.length){
                help[i++]=arr[p2++];
            }
        }else
        if (p2>R){
            while(i<help.length){
                help[i++]=arr[p1++];
            }
        }
        for (int j = 0; j < help.length; j++) {
            arr[L++]=help[j];
        }
    }


    public static void main(String[] args) {
//        MergeSort.mergeSort();
        int[] arr={2,12,5,4,8,7,9,8,10};
        mergeSort2(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
